package com.example.garbage;

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.*;

import java.util.Arrays;

public class SelectCandidatesForCoverage {
    static {
        Loader.loadNativeLibraries();
    }

    public static void main(String[] args) {
        int numDemandPoints = 5;
        int numCandidates = 10;
        int p = 3;
        int[] demands = {10, 15, 8, 12, 20};
        double[][] distances = {
                {50, 60, 70, 80, 90, 100, 110, 120, 130, 140},
                {30, 40, 50, 60, 70, 80, 90, 100, 110, 120},
                {80, 90, 70, 110, 120, 130, 140, 150, 160, 170},
                {110, 120, 130, 70, 150, 160, 170, 180, 190, 200},
                {70, 80, 90, 100, 110, 120, 130, 140, 150, 160}
        };

        // 创建线性规划求解器
        MPSolver solver = new MPSolver("SelectCandidatesForCoverage", MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING);

        // 创建变量
        MPVariable[][] x = new MPVariable[numDemandPoints][numCandidates];
        for (int i = 0; i < numDemandPoints; i++) {
            for (int j = 0; j < numCandidates; j++) {
                x[i][j] = solver.makeIntVar(0, 1, "x[" + i + "][" + j + "]");
            }
        }

        MPVariable[] selectedCandidates = new MPVariable[numCandidates];
        for (int j = 0; j < numCandidates; j++) {
            selectedCandidates[j] = solver.makeIntVar(0, 1, "selected[" + j + "]");
        }

        // 添加选择p个候选点的约束
        MPConstraint selectConstraint = solver.makeConstraint(p, p);
        for (int j = 0; j < numCandidates; j++) {
            selectConstraint.setCoefficient(selectedCandidates[j], 1);
            for (int i = 0; i < numDemandPoints; i++) {
                MPConstraint linkConstraint = solver.makeConstraint(0, 0);
                linkConstraint.setCoefficient(x[i][j], 1);
                linkConstraint.setCoefficient(selectedCandidates[j], -1);
            }
        }

        // 设置优化目标
        MPObjective objective = solver.objective();
        for (int i = 0; i < numDemandPoints; i++) {
            for (int j = 0; j < numCandidates; j++) {
                objective.setCoefficient(x[i][j], distances[i][j]);
            }
        }
        objective.setMinimization();

        // 添加每个需求点只分配到一个候选点的约束
        for (int i = 0; i < numDemandPoints; i++) {
            MPConstraint demandConstraint = solver.makeConstraint(1, 1);
            for (int j = 0; j < numCandidates; j++) {
                demandConstraint.setCoefficient(x[i][j], 1);
            }
        }

        // 添加服务容量约束
        for (int j = 0; j < numCandidates; j++) {
            MPConstraint capacityConstraint = solver.makeConstraint(0, demands[j]);
            for (int i = 0; i < numDemandPoints; i++) {
                capacityConstraint.setCoefficient(x[i][j], demands[j]);
            }
        }

        // 解决线性规划问题
        MPSolver.ResultStatus resultStatus = solver.solve();

        // 输出结果
        if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
            System.out.println("最优解找到！");

            System.out.println("需求点与候选点的分配关系：");
            for (int i = 0; i < numDemandPoints; i++) {
                System.out.print("需求点 " + i + " 分配到：");
                for (int j = 0; j < numCandidates; j++) {
                    if (x[i][j].solutionValue() == 1) {
                        System.out.print("候选点 " + j + ", ");
                    }
                }
                System.out.println();
            }
        } else {
            System.out.println("无法找到最优解。");
        }
    }
}
